/*
 * @lc app=leetcode.cn id=34 lang=javascript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

 const firstPosition = function(arr, target){
  let head = 0, tail = arr.length - 1, mid;
  while(head < tail){
    // 下去整
    mid = (head + tail) >> 1;
    if(arr[mid] >= target) {
      tail = mid;
    } else {
      head = mid + 1;
    }
  }
  
  return arr[head] === target ? head : -1;
}
const lastPosition = function(arr, pos){
  let head = pos, tail = arr.length - 1, mid, target = arr[pos];
  while(head < tail){
    // 上取整
    mid = (head + tail + 1) >> 1;
    if(arr[mid] > target){
      tail = mid - 1;
    } else {
      head = mid;
    }
  }
  return arr[head] === target ? head : -1;
}
var searchRange = function(nums, target) {
  let ret = [];
  ret[0] = firstPosition(nums, target);
  if(ret[0] === -1) return [-1, -1];
  ret[1] = lastPosition(nums, ret[0]);
  return ret;
};

/**
 * 复习 2021-08-04
 */
// 二分查找
var searchRange = function(nums, target) {
  let pre = 0, tail = nums.length - 1;
  let pos = -1, first = -1, last = -1;
  while(pre <= tail){
    let mid = pre + ((tail - pre) >> 1);
    if( nums[mid] === target ){
      pos = mid;
      break;
    }
    if(nums[mid] < target) {
      pre = mid + 1;
    } else {
      tail = mid - 1;
    }
  }
  let temp = pos;
  first = temp;
  while(nums[--temp] === target){
    first = temp;
  }
  temp = pos;
  last = temp;
  while(nums[++temp] === target){
    last = temp;
  }
  return [first, last];
}
// @lc code=end

